/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/maximal-rectangle
   @Language: C++
   @Datetime: 19-07-08 17:59
   */

class Solution {
	int largestRectangleArea(vector<int>& heights) {
		stack<int> pos; // MaxStack
		int mx=0, i=0;
		for(heights.push_back(0); i<heights.size(); pos.push(i++)){
			while(pos.size() && heights[pos.top()]>heights[i]){
				int h=heights[pos.top()];
				pos.pop();
				mx=max(mx,pos.size()?(i-pos.top()-1)*h:i*h);
			}
		}
		return mx;
	}
public:
	int maximalRectangle(vector<vector<char>>& matrix) {
		if(matrix.size()<1 || matrix[0].size()<1) return 0;
		int m=matrix.size(), n=matrix[0].size(), area=0;
		vector<int> heights(n,0);
		for(const auto &row:matrix){
			for(int i=0; i<n; ++i)
				heights[i]=row[i]=='1'?heights[i]+1:0;
			area=max(area,largestRectangleArea(heights));
		}
		return area;
	}
};
